package com.fengye.algorithms.leecode;

import java.util.ArrayDeque;
import java.util.HashMap;
import java.util.Map;
import java.util.Queue;

/**
 * @Author fengye
 * @Date 2023/4/14 11:08
 **/
public class RottingOranges994 {
    public static void main(String[] args) {
        int[][] grid = {
                {2,1,1},{1,1,0},{0,1,1}
        };
        new RottingOranges994().orangesRotting(grid);
    }

    public int orangesRotting(int[][] grid) {

        // dr,dc 配合使用得到 grid[r][c] 上grid[r-1][c]左grid[r][c-1]下grid[r+1][c]右grid[r][c+1]的元素
        int[] dr = new int[]{-1, 0, 1, 0};
        int[] dc = new int[]{0, -1, 0, 1};

        // 获取二维数组的行数row 和 列数 column
        int R = grid.length, C = grid[0].length;

        // queue : all starting cells with rotten oranges
        Queue<Integer> queue = new ArrayDeque();
        Map<Integer, Integer> depth = new HashMap();
        for (int r = 0; r < R; ++r) {
            for (int c = 0; c < C; ++c) {
                if (grid[r][c] == 2) {
                    int code = r * C + c;  // 转化为索引唯一的一维数组
                    queue.offer(code); //存储腐烂橘子
                    depth.put(code, 0); //存储橘子变为腐烂时的时间,key为橘子的一维数组下标，value为变腐烂的时间
                }
            }
        }

        int ans = 0;
        while (!queue.isEmpty()) {
            int code = queue.poll();
            int r = code / C, c = code % C;
            for (int k = 0; k < 4; ++k) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
                    grid[nr][nc] = 2;
                    int ncode = nr * C + nc;
                    queue.add(ncode);
                    // 计次的关键 元素 grid[r][c] 的上左下右元素得腐烂时间应该一致
                    depth.put(ncode, depth.get(code) + 1);
                    ans = depth.get(ncode);
                }
            }
        }

        //检查grid，此时的grid能被感染已经都腐烂了，此时还新鲜的橘子无法被感染
        for (int[] row: grid) {
            for (int v : row) {
                if (v == 1) {
                    return -1;
                }
            }
        }
        return ans;

    }

    public int orangesRotting2(int[][] grid) {
        int count = 0;
        for(int i=0;i < grid.length; i++) {
            for(int j=0;j<grid[0].length;j++){
                 count = doRotting(grid, i, j);
            }
        }
        return count;
    }

    public int doRotting(int[][] grid, int r, int c) {
        if(r<0 || r>grid.length-1 || c<0 || c>grid[0].length-1) {
            return 0;
        }

        if(grid[r][c] != 1) {
            return 0;
        }
        // 腐烂了
        grid[r][c] = 2;
        int count = 1;
        int n = 0;
        int[][] visited = {{1,0}, {-1,0}, {0,1},{0,-1}};
        for(int i=0;i<visited.length;i++) {
            n = doRotting(grid, r + visited[i][0], c + visited[i][1]);
        }
        if(n > 0) {
            count++;
        }
        return count;

    }
}
